class Solution {
public:
     vector<int> tmp;
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size(),0);
        return mergsort(nums,0,nums.size()-1);
    }
    
    int mergsort(vector<int>& nums,int left, int right){
        if(left >= right ) return 0;
        int middle = (left + right ) /2;
        int ret = 0;
        ret += mergsort(nums,left,middle);
        ret += mergsort(nums,middle+1,right);
        int cur1 = left,cur2 = middle+1,i=0;
        while(cur1<= middle&&cur2 <= right){
            if((long long)nums[cur1] >(long long)2*nums[cur2]){
                ret += middle-cur1+1;
                cur2++;
            }else {
                cur1++;
            }
        }
        cur1 = left , cur2 = middle+1;
        while(cur1 <= middle && cur2 <= right){
            if(nums[cur1] < nums[cur2])  tmp[i++] = nums[cur1++];
            else tmp[i++] = nums[cur2++];          
        }
        while(cur1 <= middle) tmp[i++] = nums[cur1++];
        while(cur2 <= right ) tmp[i++] = nums[cur2++];
        for(int i = left ; i <= right ; i++){
            nums[i] = tmp[i-left];
        }
        return ret;
    }
};